
/*
高斯消元异或线性基
性质：1. 每个答案的最高位1只有一个
*/
template<class T>
vector<T> xorbase(vector<T> a) {
    if (a.size() == 0) return {};
    
    int n = a.size(), k = 0;
    T mx = *max_element(a.begin(), a.end());
    if (mx <= 0) return {};

    for (int j = __lg(mx); j >= 0; j--) {
        for (int i = k; i < n; i++) {
            if (a[i] >> j & 1) { swap(a[i], a[k]); break; }
        }
        if ((a[k] >> j & 1) == 0) continue;
        for (int i = 0; i < n; i++) {
            if (i == k) continue;
            if (a[i] >> j & 1) a[i] ^= a[k];
        }
        k++; if (k >= n) break;
    }
    return vector<T>(a.begin(), a.begin() + k);
}


/*
min25筛第一部分，求质数的多项式和。
 */
vector<int> visi, pri; int cpri;
void init(int N) {
    N++;
    visi.assign(N, 0), pri.assign(N, 0);
    for (int i = 2; i < N; i++) {
        if (!visi[i]) {
            visi[i] = i;
            pri[++cpri] = i;
        }
        for (int j = 1; j <= cpri; j++) {
            int id = pri[j] * i;
            if (id >= N) break;
            visi[id] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
struct min25 {
    // 幂次k=1
    ll sn, n;
    vector<int> id;
    vector<ll> g;
    int getid(ll x) {
        if (x <= sn) return x;
        return id[n / x];
    }
    min25(ll N) {
        n = N;
        sn = sqrt((long double)n);
        init(2 * sn + 10); // todo

        id.assign(sn + 1, 0);
        g.assign(sn * 2 + 1, 0);
        vector<ll> big(sn * 2 + 1), G(sn + 1);
        
        for (int i = 2; i <= sn; i++) {
            G[i] = G[i - 1] + (visi[i] == i);
        }
        for (int i = 1; i <= sn; i++) {
            id[i] = 2 * sn + 1 - i;
            big[i] = i, big[id[i]] = n / i;
        }

        for (int i = 1; i <= sn * 2; i++) {
            g[i] = big[i] - 1; // todo 除了1所有数的k次方前缀和
        }

        for (int j = 1, beg = 1; pri[j] <= sn; j++) {
            while (j > 1 && beg <= sn * 2 && pri[j] * 1ll * pri[j] > big[beg]) beg++;
            for (int i = sn * 2; i >= beg; i--) {
                ll k = 1; // todo pri[j] ^ k
                g[i] = g[i] - k * (g[getid(big[i] / pri[j])] - G[pri[j - 1]]);
            }
        }
    }
    ll get(ll n) {
        return g[getid(n)];
    }
};



/*
左偏树、可并堆合并操作。
*/
vector<int> v(n + 1), l(n + 1), r(n + 1), d(n + 1), del(n + 1);
d[0] = -1;
for (int i = 1; i <= n; i++) cin >> v[i];
function<int(int, int)> merge = [&] (int x, int y) {
    if (!x || !y) return x + y;
    if ((v[x] == v[y] && x > y) || (v[x] > v[y])) swap(x, y);
    r[x] = merge(r[x], y);
    d[x] = d[r[x]] + 1;
    if (d[l[x]] < d[r[x]]) swap(l[x], r[x]);
    return x;
};


/*
fhqtreap
*/
mt19937 rd(time(0));
int gen(int l, int r) {return rd() % (r - l + 1) + l;}
#define getsz(x) (x ? x->sz : 0)
#define getv(x) (x ? x->v : 0)
// todo
struct Node {
    Node* l,* r;
    int pri, v, sz;
    bool rev;
    Node(int v_ = 0) {
        l = r = NULL;
        pri = gen(0, 1e7), sz = 1, v = v_, rev = 0;
    }    
    // Info todo

    void push_up() {
        sz = getsz(l) + getsz(r) + 1;
        // todo
    }
    void push_down() {
        // todo
        if (rev) {
            swap(l, r);
            if (l) l->rev ^= 1;
            if (r) r->rev ^= 1;
            rev = 0;
        }
    }
};

// k num give u
void split(Node* x, Node*& u, Node*& v, int k) {
    if (x == NULL) {
        u = v = NULL; return;
    }
    x->push_down();
    if (getsz(x->l) + 1 <= k) {
        u = x;
        split(x->r, u->r, v, k - getsz(x->l) - 1);
        u->push_up();
    } else {
        v = x;
        split(x->l, u, v->l, k);
        v->push_up();
    }
}
// allv(u) <= allv(v)
Node* merge(Node* u, Node* v) {
    if (!u) return v; if (!v) return u;
    if (u->pri < v->pri) {
        u->push_down();
        u->r = merge(u->r, v);
        u->push_up();
        return u;
    } else {
        v->push_down();
        v->l = merge(u, v->l);
        v->push_up();
        return v;
    }
}



/*
dinic
带上下界网络流
*/
template<class T>
struct Flow {
    const int inf = 1e9;
    struct edge {
        int v; T w; int ne; 
    };
    int n;
    vector<edge> e;
    vector<int> head, now, dep;
    
    vector<T> in; // 上下界用到
    Flow (int n_) : n(n_) {
        e.resize(2);
        int N = n + 10;
        head.resize(N), now.resize(N), dep.resize(N);
        in.resize(N);
    }
    void add_edge(int u, int v, T w) {
        e.push_back((edge){v, w, head[u]});
        head[u] = e.size() - 1;
    }
    void add(int u, int v, T w) {
        add_edge(u, v, w); add_edge(v, u, 0);
    }
    // 上下界用到
    void add(int u, int v, T l, T r) {
        in[v] += l, in[u] -= l;
        add(u, v, r - l);
    }

    bool bfs(int s, int t) {
        fill(dep.begin(), dep.end(), inf);
        dep[s] = 0, now[s] = head[s];
        queue<int> q; q.push(s);
        while(q.size()) {
            int u = q.front(); q.pop();
            for(int i = head[u]; i; i = e[i].ne) {
                int v = e[i].v;
                if(e[i].w > 0 && dep[v] == inf) {
                    q.push(v);
                    now[v] = head[v], dep[v] = dep[u] + 1;
                    if(v == t) return 1;
                }
            }
        }
        return 0;
    }
    T dfs(int u, int t, T sum) {
        if(u == t) return sum;
        T k, flow = 0;
        for(int i = now[u]; i > 0 && sum > 0; i = e[i].ne) {
            now[u] = i; int v = e[i].v;
            if(e[i].w > 0 && (dep[v] == dep[u] + 1)) {
                k = dfs(v, t, min(sum, (T)e[i].w));
                if(k == 0) dep[v] = inf;
                e[i].w -= k; e[i ^ 1].w += k, flow += k, sum -= k;
            }
        } 
        return flow;
    }
    
    T wk(int s, int t) {
        T ans = 0;
        while(bfs(s, t)) ans += dfs(s, t, numeric_limits<T>::max());
        return ans;
    }
    // 上下界用到
    T wklr(int s, int t, int ismin = 0) {
        T ans = 0, tot = 0;
        int ss = n + 1, tt = n + 2;
        for (int i = 0; i <= n; i++) {
            if (in[i] > 0) add(ss, i, in[i]), tot += in[i];
            else add(i, tt, -in[i]);
        }
        add(t, s, numeric_limits<T>::max());
        ans = wk(ss, tt);
        if (tot != ans) {
            return -1;
        }
        int cc = e.size();
        ans = e[cc - 1].w;
        e[cc - 1].w = 0, e[cc - 2].w = 0;
        return ans + (ismin ? -wk(t, s) : wk(s, t));
    }
    vector<vector<pair<int, T>>> show() {
        vector E(n + 1, vector<pair<int, T>>());
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, ne] = e[i];
                E[u].push_back({v, w});
            }
        }
        return E;
    }
    vector<pii> minCut(int s) {
        queue<int> q;
        q.push(s);
        vector<int> visi(n + 1);
        visi[s] = 1;
        while (q.size()) {  
            auto u = q.front(); q.pop();
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[v] || w == 0) continue;
                visi[v] = 1;
                q.push(v);
            }
        }
        vector<pii> ans;
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[u] ^ visi[v]) {
                    ans.push_back({u, v});
                }
            }
        }
        return ans;
    }
};



/*
上下界最小费用最大流，用得不多，不一定对
*/
template<class T>
struct MCMF {
    struct edge {
        int v; T c, w; int ne;
    };
    int n;
    vector<edge> e;
    vector<int> head, pre;
    vector<bool> visi;
    vector<T> d, mf;
    vector<T> in; T totcost;// 上下界
    MCMF(int n_) : n(n_) {
        totcost = 0;
        int N = n + 10; e.resize(2);
        head.resize(N), d.resize(N), mf.resize(N), pre.resize(N), visi.resize(N), in.resize(N);
    }
    void add_edge(int u, int v, T c, T w) {
        e.push_back({v, c, w, head[u]}); head[u] = e.size() - 1;
    }
    void add(int u, int v, T c, T w) {
        add_edge(u, v, c, w); add_edge(v, u, 0, -w);
    }
    void add(int u, int v, T l, T r, T w) {
        totcost += l * w;
        in[v] += l, in[u] -= l;
        add(u, v, r - l, w);
    }
    bool spfa(int s, int t) {
        fill(d.begin(), d.end(), numeric_limits<T>::max());
        fill(mf.begin(), mf.end(), 0);
        queue<int> q; q.push(s);
        d[s] = 0, mf[s] = numeric_limits<T>::max(), visi[s] = 1;
        while(q.size()) {
            int u = q.front(); q.pop(); visi[u] = 0;
            for(int i = head[u]; i; i = e[i].ne) {
                auto [v, c, w, _] = e[i];
                if(d[v] > d[u] + w && c) {
                    d[v] = d[u] + w, mf[v] = min(mf[u], c);
                    pre[v] = i;
                    if(!visi[v]) q.push(v), visi[v] = 1;
                }
            }
        }
        return mf[t] > 0;
    }
    array<T, 2> wk(int s, int t) {
        T flow = 0, cost = 0;
        while(spfa(s, t)) {
            for(int v = t; v != s; ) {
                int i = pre[v]; 
                e[i].c -= mf[t]; e[i ^ 1].c += mf[t];
                v = e[i ^ 1].v;
            }
            flow += mf[t], cost += mf[t] * d[t];
        }
        return {flow, cost};
    }
    /*
    有源汇上下界最小费用最大流
    */
    array<T, 2> wklr(int s, int t) {
        int ss = n + 1, tt = n + 2;
        T tot = 0;

        for (int i = 0; i <= n; i++) {
            if (in[i] > 0) add(ss, i, in[i], 0), tot += in[i];
            else if (in[i] < 0) add(i, tt, -in[i], 0);
        }
        add(t, s, numeric_limits<T>::max(), 0);
        auto res = wk(ss, tt);
        if (res[0] != tot) {
            return {-1, -1};
        }
        int cnt = e.size();
        res[0] = e[cnt - 1].c;
        e[cnt - 1].c = e[cnt - 2].c = 0;
        auto res1 = wk(s, t);
        res[0] += res1[0], res[1] += res1[1] + totcost;
        return res;
    }
};

